#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int MAXN = 1010;
const int mod = 1e9+7;

int k,n,a[MAXN],goal,num[MAXN];
char s[MAXN];
ll f[MAXN][MAXN];

void predo(){
	f[0][0] = 1;
	for(int i = 1;i <= 1000;i++){
		f[i][0] = 1,f[i][i] = 1;
		for(int j = 1;j < i;j++) f[i][j] = (f[i-1][j] + f[i-1][j-1]) % mod;
	}
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	scanf("%s",s+1); n = strlen(s+1); for(int i = 1;i <= n;i++) a[i] = s[i] ^ 48;
	scanf("%d",&k); if(k == 0) {puts("1");return 0;}ll ans = 0;
	predo();
	for(int i = 2;i <= n;i++) num[i] = num[__builtin_popcount(i)] + 1;
	for(int i = 1;i <= n;i++){
		if(num[i] + 1 == k){
			int tmp = i;
			for(int j = 1;j <= n && tmp >= 0;j++)
				if(a[j] == 1) ans = (ans + f[n-j][tmp]) % mod,tmp--;
			if(tmp == 0) ans = (ans + 1)%mod;
		}
	}if(k == 1) ans = (ans - 1 + mod)%mod;
	printf("%lld\n",ans);
	return 0;
}

